Networks are used to connect multiple devices, such as computers. A Mobile Ad hoc Network or MANET consists of two or more potentially mobile devices, often referred to as “nodes,” that form a self-organizing network. Data is usually broken into “packets” that are sent from one device to another. The devices communicate wirelessly by relaying or forwarding data across the network through a sequence of wireless packet transmissions, hopping from one node to another. A sequence of transmissions that enables data from a given source to reach a specific destination is referred to as a route. One route might involve only two nodes: the source and destination. Another route might involve three nodes: the source node, a neighboring node in range of the source, and the destination node. Other routes might include several, or dozens, or even more neighboring or intermediate nodes between the source and the destination. A MANET uses a routing protocol to determine the route between sources and destinations.
In a MANET the devices may join and leave the network at any time. The dynamic nature of the network requires a routing protocol that can handle such frequent topological changes. The two primary categories of routing protocols used in MANET's are proactive and reactive. Proactive routing protocols actively track routes between all nodes in the network regardless of whether or not the nodes are actively sending or receiving data packets. Reactive protocols setup routes on-demand when a source has data that needs to be delivered to a specific destination. Despite their differences in approach, both techniques generally select a single route on which data is forwarded from a given source to a destination. The selection of a single route is generally determined by a number of factors, including hop count, signal-to-noise ratio, delay, data-link rates, and reliability. These factors can be used to establish a link metric that the routing protocol accumulates in order to determine a preferred communication route from a source to a destination.
Another significant challenge to MANET routing protocols is that the quality of the wireless links in the network continuously changes. Changes occur due to the mobility of nodes and changes in the environment that result in channel fading and fluctuating link characteristics. As the link characteristics continuously change, the link metrics change. If changing link metrics between a source and a destination favor changing routes, and if the protocol is aware of the changed link metrics, then the protocol will change the route from the one currently selected to one with better link metrics. A routing protocol that is able more accurately and quickly to adapt to the continuously changing channel conditions is able to achieve higher performance and improved overall network efficiency.
MANET routing protocols typically use control packets—that travel along with or separate from the data packets—to exchange information that is used to select and establish routes. The control packets generally contain a metric that represents either the cost of a link or the accumulated cost of a path. They also generally contain a sequence number that enables the protocol to determine a temporal ordering of the information. The routing protocol processes a sequence of asynchronous information, meaning that topology updates will not necessarily be received by neighboring nodes in any particular order. In addition, the wireless medium is susceptible to packet loss resulting in transmissions that are not received. The asynchronous lossy environment in which MANET routing protocols operate can result in a protocol learning information about routes with an inferior routing metrics before they eventually learn of routes with better routing metrics.
In a routing protocol, nodes typically establish and maintain routes to destinations by the use of routing “advertisements” in control packets. The specific contents that comprise a route advertisement vary depending on the routing protocol, but generally receiving an advertisement updates a node's knowledge of its available forwarding options. A node's forwarding options for a particular destination consist of the set of possible next hops (neighboring nodes) and a metric for each of these options. In a number of known routing protocols, a node must make an advertisement based on the information it received so that the link metrics about a route will propagate through all the nodes in the network.
Once a node has selected a next hop, and made an advertisement under a given sequence number, it is generally restricted on changing it's next hop selection, since other nodes may have already made next hop selections and advertisements that were based on the node's previous advertisement. The hop-by-hop metric-accumulation process often used by MANET routing protocols creates a transitive dependency on the information shared between nodes. If nodes in the network changed their advertisements (within the context of a single sequence number) “routing loops” could occur in the network.
A routing loop exists when routing-state information creates an endless cycle. When packets are routed in a loop, they do not reach their intended destination and instead are fruitlessly retransmitted, consuming shared resources (e.g., the wireless-medium time). In most existing routing protocols, loops occur because of delays in disseminating updated topology information. Some ways are known for designing routing protocols that never create routing loops. These protocols may be described as “instantaneously loop free.”
In order to make sure that the routing protocol makes decisions based on all the available information, time delays or settling times are typically employed. These delays are designed to allow a node to wait long enough that there is confidence that it will not hear any newer information (for a given route and sequence number tuple) before it commits to making an advertisement using that sequence number. These time delays accumulate (as routing updates propagate), resulting in significant delays in a node's ability to receive updated topological information.
In an attempt to minimize the undesirable delay in information propagation, some known protocols use adaptive-delay mechanisms, in which the nodes compute the average difference in time from the first received advertisement for a given sequence number until the best received advertisement under the same sequence number. But some delay still exists in these protocols.
It would be desirable to have systems and methods that implement routing protocols that allow the information to propagate instantly, and that are instantaneously loop free.